package arrAndstr;

/*
    45. 跳跃游戏 II
*/
public class T45 {

    public static void main(String[] args) {
        int[] array = new int[]{2,3,1};

        System.out.println(jump(array));
    }

    public static int jump(int[] nums) {
        // 向后跳，每次获取的index为nums[index]+index最大（思路和上道题一致）
        int len = nums.length;
        int stepCount = 0;

        int index = 0;
        while (index < len-1) {  // 保证能到，不用判断0情况
            int leftIndex = index + 1;
            int rightIndex = index +nums[index];
            index = findNextIndex(nums, leftIndex, rightIndex);
            stepCount++;
            if (rightIndex >= len-1) {
                break;
            }
        }

        return stepCount;
    }

    public static int findNextIndex(int[] array, int leftIndex, int rightIndex) {
        int len = array.length;
        int maxLen = leftIndex + array[leftIndex];
        int maxIndex = leftIndex;
        for(int i=leftIndex; i<=rightIndex && i<len; i++) {
            if(array[i] + i >= maxLen) {
                maxLen = array[i] + i;
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}
